package com.explorati.LeetCode343.integerBreak;

import java.util.Arrays;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 12:38 2020/10/7 0007
 * @ Description ：
 */
public class Solution {

    /**
     * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
     *
     * 输入: 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
     *
     * @param n
     * @return
     */
    public int integerBreak(int n) {
        int[] res = new int[n + 1];
        Arrays.fill(res, -1);
        res[1] = 1;

        for(int i = 2; i <= n;  i++) {
            //分割乘积，先计算2 = 1 * 1，j = 1, res = j * (i - j)
            // 3 = integerBreak(2) 的最大值 * 1 + integerBreak(1)的最大值 * 2
            for(int j = 1; j < i; j++) {
                // res[i]: 最初为-1，当j ++后，当前数的分解后最大乘积应该 这个数-可以拆解的数(i - j) * 当前拆解的数(J)
                // 在向下分解时为当前分解的数j * 剩余的数继续向下分解的最大乘积
//                res[i] = max3(res[i], j * (i - j), j * integerBreak(i - j));
                //由于res[i - j]必定存在
                res[i] = max3(res[i], j * (i - j), j * res[i - j]);
            }
        }

        return res[n];
    }

    private int max3(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }
}
